মের্জ সর্ট এবং কোয়িক সর্ট

মের্জ সর্ট এবং কোয়িক সর্ট হল দুটি জনপ্রিয় সোর্টিং অ্যালগরিদম যা তাদের কার্যকারিতা ও গতি কারণে ব্যাপকভাবে ব্যবহৃত হয়। নিচে উভয় অ্যালগরিদমের বর্ণনা, কাজের পদ্ধতি, এবং উদাহরণ দেওয়া হয়েছে।

১. মের্জ সর্ট (Merge Sort)

বর্ণনা

মের্জ সর্ট একটি ডিভাইড এবং কনকার (divide and conquer) অ্যালগরিদম। এটি একটি তালিকাকে দুটি সমান অংশে বিভক্ত করে এবং তারপর প্রতিটি অংশকে পৃথকভাবে সনির্দেশ করে। শেষে দুটি সাজানো অংশকে একত্রিত (merge) করে একটি সম্পূর্ণ সাজানো তালিকা তৈরি করে।

পদ্ধতি

1. যদি তালিকার আকার 1 বা তার কম হয়, তাহলে তা স্বয়ংসম্পূর্ণ।
2. তালিকাটি দুইটি সমান অংশে বিভক্ত করুন।
3. প্রতিটি অংশকে মের্জ সর্ট ব্যবহার করে সাজান।
4. সাজানো দুটি অংশকে একত্রিত করুন।

উদাহরণ কোড (Python):

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # তালিকা বিভক্ত করা
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)  # বাম অংশ সাজানো
        merge_sort(right_half)  # ডান অংশ সাজানো

        i = j = k = 0

        # বাম এবং ডান অংশ একত্রিত করা
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # বাকি এলিমেন্টগুলো কপি করা
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# উদাহরণ
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array is:", arr)  # Output: [3, 9, 10, 27, 38, 43, 82]

২. কোয়িক সর্ট (Quick Sort)

বর্ণনা

কোয়িক সর্টও একটি ডিভাইড এবং কনকার অ্যালগরিদম, তবে এটি একটি পিভট এলিমেন্ট ব্যবহার করে। এটি তালিকাকে পিভটের ভিত্তিতে বিভক্ত করে এবং পিভটের বাম এবং ডানে থাকা এলিমেন্টগুলিকে পৃথক করে সাজায়।

পদ্ধতি

1. একটি পিভট এলিমেন্ট নির্বাচন করুন (যেকোনো এলিমেন্টকে পিভট হিসেবে নেওয়া যায়)।
2. তালিকাকে পিভটের তুলনায় ছোট এবং বড় অংশে বিভক্ত করুন।
3. পিভটের বাম এবং ডানে থাকা অংশগুলিকে আলাদাভাবে কোয়িক সর্ট ব্যবহার করে সাজান।
4. সব অংশ সাজানোর পরে, পিভটকে সঠিক স্থানে রাখুন।

উদাহরণ কোড (Python):

def quick_sort(arr):
    if len(arr) <= 1:  # যদি তালিকা 0 বা 1 এলিমেন্টের হয়
        return arr
    else:
        pivot = arr[len(arr) // 2]  # পিভট নির্বাচন
        left = [x for x in arr if x < pivot]  # পিভটের চেয়ে ছোট
        middle = [x for x in arr if x == pivot]  # পিভট
        right = [x for x in arr if x > pivot]  # পিভটের চেয়ে বড়
        return quick_sort(left) + middle + quick_sort(right)  # অংশগুলিকে একত্রিত করা

# উদাহরণ
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)  # Output: [3, 9, 10, 27, 38, 43, 82]

তুলনা: মের্জ সর্ট বনাম কোয়িক সর্ট

উপসংহার

মের্জ সর্ট এবং কোয়িক সর্ট উভয়ই জনপ্রিয় সোর্টিং অ্যালগরিদম। মের্জ সর্ট সাধারণত স্থিতিশীল এবং নিম্ন গড় সময় জটিলতা প্রদান করে, তবে এটি অতিরিক্ত স্থান ব্যবহার করে। কোয়িক সর্ট গড় সময় জটিলতা এবং ইন-প্লেস প্রক্রিয়ার কারণে সাধারণত কার্যকরী, তবে এর ক্ষেত্রে সবচেয়ে খারাপ পরিস্থিতি O(n²) হতে পারে। উভয় অ্যালগরিদমের নিজস্ব সুবিধা এবং অসুবিধা রয়েছে, তাই সঠিক পরিস্থিতিতে সঠিক অ্যালগরিদম নির্বাচন করা গুরুত্বপূর্ণ।